/*
 * Copyright (C), 2015-2018
 * FileName: Solution206
 * Author:   zhao
 * Date:     2018/9/25 11:17
 * Description: 206. 反转链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredthree;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈206. 反转链表〉
 *
 * @author zhao
 * @date 2018/9/25 11:17
 * @since 1.0.1
 */
public class Solution206 {

  /**************************************
   * 题目
   反转一个单链表。

   示例:

   输入: 1->2->3->4->5->NULL
   输出: 5->4->3->2->1->NULL
   进阶:
   你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
   **************************************/

  /**************************************
   *
   * 想法：
   *    一、迭代：
   *        从左到右修改next值
   *          1->2->3->4->5->NULL
   *          null<-1   2->3->4->5->NULL
   *          null<-1<-2   3->4->5->NULL
   *          null<-1<-2<-3    4->5->NULL
   *          null<-1<-2<-3<-4<-   5->NULL
   *          null<-1<-2<-3<-4<-5   NULL
   *
   *
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *          1->2->3->4->5->NULL
   *          null<-1   2->3->4->5->NULL
   *          null<-1<-2   3->4->5->NULL
   *          null<-1<-2<-3    4->5->NULL
   *          null<-1<-2<-3<-4<-   5->NULL
   *          null<-1<-2<-3<-4<-5   NULL
   * 总结：
   *
   * ***********************************/
  public ListNode reverseList(ListNode head) {
    ListNode curNode = head;
    ListNode preNode = null;
    ListNode nextNode = null;

    while (curNode != null) {
      nextNode = curNode.next;
      curNode.next = preNode;

      preNode = curNode;
      curNode = nextNode;
    }

    return preNode;
  }

  /**************************************
   * 比我好的答案 better
   * 递归解法
   * ***********************************/
  public ListNode recReverseList(ListNode head) {
    if (head == null) {
      return null;
    }
    if (head.next == null) {
      return head; // 递归边界
    }
    ListNode pointer = recReverseList(head.next); // 递归主体 递归函数 向下递归

    // 发现 递归外面 有些操作没有完成 并且不能放在递归之前进行 一下代码在递归返回时执行
    head.next.next = head;
    // 对于头节点 将其next 指针改为null
    if (head.next.next == head) {
      head.next = null;
    }
    // 也可写为 head.next = null; 在每个递归里 将head.next = null 比较冗余
    // 因为递归 编译器保存了上一层递归的信息 因此能够返回
    return pointer;
  }

}
